package cn.edu.jxau.test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

/**
 * HDOJ 1872
 * http://blog.csdn.net/liu6886/article/details/50915244
 * http://www.cnblogs.com/hss-521/p/7227608.html
 * http://blog.csdn.net/zhaihao1996/article/details/51959326
 * 
 * @author 付大石
 */

public class Main {

    public static void main(String[] args) {

        String[] arr = new String[] { "aa 10", "bb 10", "cc 20" };
        String[] result = new String[] { "cc 20", "bb 10", "aa 10" };
        judge(arr, result);
        arr = new String[] { "aa 10", "bb 10", "cc 20" };
        result = new String[] { "cc 20", "aa 10", "bb 10" };
        judge(arr, result);
        arr = new String[] { "aa 10", "bb 10", "cc 20" };
        result = new String[] { "aa 10", "bb 10", "cc 20" };
        judge(arr, result);
    }

    private static void judge(String[] arr, String[] result) {

        Student[] stuArr = new Student[arr.length];
        Student[] resultArr = new Student[result.length];
        for (int i = 0; i < arr.length; i++) {
            String[] arrSplit = arr[i].split(" ");
            stuArr[i] = new Student(arrSplit[0], Integer.parseInt(arrSplit[1]), i);
            String[] resultSplit = result[i].split(" ");
            resultArr[i] = new Student(resultSplit[0], Integer.parseInt(resultSplit[1]));
        }
        judge(stuArr, resultArr);
    }

    private static void judge(Student[] arr, Student[] result) {

        boolean isError = false;
        boolean isStable = true;
        // 判断result是否有序 （仅就source而言）//
        for (int i = 1; i < result.length; i++) {
            if (result[i - 1].getSource() < result[i].getSource()) { // 不是有序的
                isError = true;
                break;
            }
        }

        // 判断result是否稳定 //
        if (!isError) {
            sort(arr);
            for (int i = 0; i < arr.length; i++) {
//                if (!arr[i].getName().equals(result[i].getName())) {
//                    if (arr[i].getSource() == result[i].getSource()) {
//                        isStable = false;
//                    }
//                }
                if (arr[i].getSource() == result[i].getSource()) {
                    if (!arr[i].getName().equals(result[i].getName())) {
                        isStable = false;
                    }
                }
            }
        }

        // 输出结果 //
        if (isError) {
            System.out.println("Error");
        } else if (!isStable) {
            System.out.println("No Stable");
        } else {
            System.out.println("Right");
        }
    }

    /**
     * 使用稳定的归并排序
     * @param arr
     */
    private static <T extends Comparable<T>> void sort(T[] arr) {
        T[] aux = (T[]) new Comparable[arr.length];
        sort(aux, arr, 0, arr.length - 1);
    }

    private static <T extends Comparable<T>> void sort(T[] aux, T[] arr, int low, int high) {

        if (high <= low) {
            return;
        }
        int mid = low + ((high - low) >> 1);
        sort(aux, arr, low, mid);
        sort(aux, arr, mid + 1, high);
        merge(aux, arr, low, mid, high);
    }

    private static <T extends Comparable<T>> void merge(T[] aux, T[] arr, int low, int mid, int high) {

        int i = low;
        int j = mid + 1;
        for (int k = low; k <= high; k++) {
            aux[k] = arr[k];
        }
        int cursor = low;
        while (i <= mid && j <= high) {
            if (aux[i].compareTo(aux[j]) < 0) {
                arr[cursor++] = aux[i++];
            } else {
                arr[cursor++] = aux[j++];
            }
        }
        while (i <= mid) {
            arr[cursor++] = aux[i++];
        }
        while (j <= mid) {
            arr[cursor++] = aux[j++];
        }
    }
}

class Student implements Comparable<Student> {

    private String name;
    private int source;
    private int id;

    public Student(String name, int source, int id) {
        this.name = name;
        this.source = source;
        this.id = id;
    }

    public Student(String name, int source) {
        this.name = name;
        this.source = source;
    }

    @Override
    public int compareTo(Student s) {

        if (source != s.source) {
            return s.source - source;
        } else {
            return id - s.id;
        }
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getSource() {
        return source;
    }

    public void setSource(int source) {
        this.source = source;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    @Override
    public String toString() {
        return "Student [name=" + name + ", source=" + source + ", id=" + id + "]";
    }
}